import sys


class Graph():

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [[0 for column in range(vertices)]

                      for row in range(vertices)]

    def printSolution(self, dist):

        print("Vertex tDistance from Source")

        for node in range(self.V):
            print(node, "t", dist[node])

    # A utility function to find the vertex with

    # minimum distance value, from the set of vertices

    # not yet included in shortest path tree

    def minDistance(self, dist, sptSet):

        # Initialize minimum distance for next node

        min = sys.maxsize

        # Search not nearest vertex not in the

        # shortest path tree

        for v in range(self.V):

            if dist[v] < min and sptSet[v] == False:
                min = dist[v]

                min_index = v

        return min_index

    # Function that implements Dijkstra's single source

    # shortest path algorithm for a graph represented

    # using adjacency matrix representation

    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V

        dist[src] = 0

        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from

            # the set of vertices not yet processed.

            # u is always equal to src in first iteration

            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the

            # shortest path tree

            sptSet[u] = True

            # Update dist value of the adjacent vertices

            # of the picked vertex only if the current

            # distance is greater than new distance and

            # the vertex in not in the shortest path tree

            for v in range(self.V):

                if self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        self.printSolution(dist)


# Driver program
if __name__=="__main__":
    g = Graph(9)

    g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],

               [4, 0, 8, 0, 0, 0, 0, 11, 0],

               [0, 8, 0, 7, 0, 4, 0, 0, 2],

               [0, 0, 7, 0, 9, 14, 0, 0, 0],

               [0, 0, 0, 9, 0, 10, 0, 0, 0],

               [0, 0, 4, 14, 10, 0, 2, 0, 0],

               [0, 0, 0, 0, 0, 2, 0, 1, 6],

               [8, 11, 0, 0, 0, 0, 1, 0, 7],

               [0, 0, 2, 0, 0, 0, 6, 7, 0]

               ]

    print(g.dijkstra(0))

# This code